/*
2022-3-6
https://leetcode-cn.com/problems/replace-non-coprime-numbers-in-array/
*/
class Solution {
public:
    int gcd(int a,int b)
    {
        return b?gcd(b,a%b):a;
    }
    int lcd(int a,int b)
    {
        return (long long)a*b/gcd(a,b);
    }
    vector<int> replaceNonCoprimes(vector<int>& nums) {
        vector<int>ans;
        int n=nums.size();
        for(int i=0;i<n;i++)
        {
            int x=nums[i];
            while(ans.size() && gcd(x,ans[ans.size()-1])>1)
            {
                x=lcd(x,ans.back());
                ans.pop_back();
            }
            ans.push_back(x);
        }
        return ans;
    }
};
